#pragma once
using namespace std;

namespace ns_list
{
    template <class T>
    struct list_node
    {
        T _data;
        list_node<T> *_next;
        list_node<T> *_prev;

        list_node(const T &x = T())
            : _data(x), _next(nullptr), _prev(nullptr)
        {
        }
    };

    // T T& T*
    // T cosnt T& const T*
    template <class T, class Ref, class Ptr>
    struct __list_iterator
    {
        typedef list_node<T> Node;
        typedef __list_iterator<T, Ref, Ptr> self;
        Node *_node;

        __list_iterator(Node *node)
            : _node(node)
        {
        }

        self &operator++()
        {
            _node = _node->_next;
            return *this;
        }

        self &operator--()
        {
            _node = _node->_prev;
            return *this;
        }

        self operator++(int)
        {
            self tmp(*this);
            _node = _node->_next;

            return tmp;
        }

        self operator--(int)
        {
            self tmp(*this);
            _node = _node->_prev;

            return tmp;
        }

        Ref operator*()
        {
            return _node->_data;
        }

        Ptr operator->()
        {
            return &_node->_data;
        }

        bool operator!=(const self &s)
        {
            return _node != s._node;
        }

        bool operator==(const self &s)
        {
            return _node == s._node;
        }
    };

    template <class T>
    class list
    {
        typedef list_node<T> Node;

    public:
        typedef __list_iterator<T, T &, T *> iterator;
        typedef __list_iterator<T, const T &, const T *> const_iterator;

        // typedef __list_const_iterator<T> const_iterator;

        const_iterator begin() const
        {
            return const_iterator(_head->_next);
        }

        const_iterator end() const
        {
            return const_iterator(_head);
        }

        iterator begin()
        {
            // return iterator(_head->_next);
            return _head->_next;
        }

        iterator end()
        {
            // return iterator(_head->_next);
            return _head;
        }

        void empty_init()
        {
            _head = new Node;
            _head->_next = _head;
            _head->_prev = _head;

            _size = 0;
        }

        list()
        {
            empty_init();
        }

        // lt2(lt1)
        list(const list<T> &lt)
        {
            empty_init();
            for (auto e : lt)
            {
                push_back(e);
            }
        }

        void swap(list<T> &lt)
        {
            std::swap(_head, lt._head);
            std::swap(_size, lt._size);
        }

        list<int> &operator=(list<int> lt)
        {
            swap(lt);

            return *this;
        }

        ~list()
        {
            clear();

            delete _head;
            _head = nullptr;
        }

        void clear()
        {
            iterator it = begin();
            while (it != end())
            {
                it = erase(it);
            }
        }

        void push_back(const T &x)
        {
            insert(end(), x);
        }

        void push_front(const T &x)
        {
            insert(begin(), x);
        }

        void pop_front()
        {
            erase(begin());
        }

        void pop_back()
        {
            erase(--end());
        }

        iterator insert(iterator pos, const T &x)
        {
            Node *cur = pos._node;
            Node *newnode = new Node(x);

            Node *prev = cur->_prev;

            // prev newnode cur
            prev->_next = newnode;
            newnode->_prev = prev;

            newnode->_next = cur;
            cur->_prev = newnode;

            ++_size;

            return iterator(newnode);
        }

		iterator erase(iterator pos)
		{
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* next = cur->_next;

			delete cur;
			prev->_next = next;
			next->_prev = prev;

			--_size;

			return iterator(next);
		}

        iterator find_order(int pos)
        {
            iterator it = begin();
            while (pos-- && it != end()) // 移动迭代器至指定位置
            {
                ++it;
            }
            return it;
        }

        iterator find(int val = 0, int *count = nullptr)
        {
            iterator it = begin();
            while (*it != val && it != end()) // 移动迭代器至指定位置
            {
                ++(*count);
                ++it;
            }
            return it;
        }

        size_t size() const
        {
            return _size;
        }

    private:
        Node *_head;
        size_t _size;
    };

    template <typename Container>
    void print_container(const Container &con)
    {
        typename Container::const_iterator it = con.begin();
        while (it != con.end())
        {
            cout << *it << " ";
            ++it;
        }
        cout << endl;
    }

}